package seqlist.oj;


class Node{
    //存储具体元素
    int data;
    //存储下一节节点的地址
    Node next;

    public Node(int data) {
        this.data = data;
    }

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

}

public class SingelLinkedListWithHead {
    private Node dummyHead=new Node(-1);
    private int size;


    //用虚拟头节点在任意位置插入元素
    public void addIndex(int index, int data){
        if(index<0 ||index>size){
            System.err.println("add index illegal");
            return;
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;//
        }
        //此时 prev就是待插入位置的前驱结点
        Node node=new Node(data);
        node.next=prev.next;
        prev.next=node;
        size++;

    }
    //头插
    public void addFirst(int data){
        addIndex(0,data);
    }
    public void addLast(int data){
        addIndex(size,data);
    }

    //删除下标对应的元素
    public void removeIndex(int index){
        if(index<0 || index>=size){
            System.err.println("remove index illegal");
            return;
        }
        Node prev=dummyHead;
        for (int i = 0; i < index; i++) {
            prev=prev.next;
        }
        //此时prev就是待删除位置的前驱结点
        Node node=prev.next;
        prev.next=node.next;
        node.next=null;
        size--;
    }



    public String toString(){
        String ret="";
       Node node=dummyHead.next;
       while(node!=null){
           ret+=node.data+"->";
           node=node.next;
       }
       ret+="NULL";
       return  ret;
    }
    public static void main(String[] args) {
        SingelLinkedListWithHead singelLinkedListWithHead=new SingelLinkedListWithHead();
        singelLinkedListWithHead.addFirst(1);
        singelLinkedListWithHead.addFirst(3);
        singelLinkedListWithHead.addLast(4);
        singelLinkedListWithHead.addIndex(1,5);
        singelLinkedListWithHead.removeIndex(1);
        System.out.println(singelLinkedListWithHead);
    }
}
